Computer systems typically comprise a combination of computer programs and hardware, such as semiconductors, transistors, chips, circuit boards, storage devices, and processors. The computer programs are stored in the storage devices and are executed by the processors. Fundamentally, computer systems are used for the storage, manipulation, and analysis of data.
One mechanism for managing data is called a database management system (DBMS) or simply a database. Many different types of databases are known, but the most common is usually called a relational database, which organizes data in tables that have rows, which represent individual entries, tuples, or records in the database, and columns, fields, or attributes, which define what is stored in each entry, tuple, or record. Each table has a unique name within the database and each column has a unique name within the particular table. The database also has one or more indexes, which are data structures that inform the DBMS of the location of a certain row in a table given an indexed column value, analogous to a book index informing the reader of the page on which a given word appears.
One way to retrieve data from a database is through statements called database queries, which may originate from user interfaces, application programs, or remote computer systems, such as clients or peers. A query is an expression evaluated by the DBMS, in order to retrieve data from the database that satisfies or meets the criteria or conditions specified in the query. Although the query requires the return of a particular data set in response, the method of query execution is typically not specified by the query. Thus, after the DBMS receives a query, the DBMS interprets the query and determines what internal steps are necessary to satisfy the query. These internal steps may comprise an identification of the table or tables specified in the query, the row or rows selected in the query, and other information such as whether to use an existing index, whether to build a temporary index or indexes, the type and contents of the index(es) to build, whether to use a temporary file to execute a sort, and/or the order in which the tables are to be joined together to satisfy the query. When taken together, these internal steps are referred to as an execution plan. The DBMS often saves the execution plan and reuses it when the user or requesting program repeats the query, which is a common occurrence, instead of undergoing the time-consuming process of recreating the execution plan.
Many different execution plans may be created for any one query, each of which would return the same data set that satisfies the query, yet the different execution plans may provide widely different performance. Thus, the execution plan selected by the DBMS needs to provide the required data at a reasonable cost in terms of time and hardware resources. One factor that contributes to the cost of a particular execution plan is the type of index or indexes that the execution plan specifies.